Notes/Domino 6 and 7 Forum : SMTP error 451 Unable to complete command, DNS not available or timed out

We are in a process of moving our Domino server from Windows NT to Linux. We've got 6.0.2 CF1 running on Linux now and generally everything works. The only problem we've been unable to figure out is with receiving mail. The server doesn't accept any mail at all, giving the message that you can see in the subject line.
We can send mail out to anywhere without any problems.

I've tried to telnet to port 25 of the Domino server from another machine, and here is the display of the session:

[toomas@mytestbox notesdata]$ telnet domino-server 25

Trying 192.168.1.6...

Connected to domino-server.our-internal-domain.
Escape character is '^]'.

220 domino-server.our-internal-domain ESMTP Service (Lotus Domino Release 6.0.2CF1) ready at Fri, 24 Oct 2003 22:49:53 +0300

HELO mytestbox

250 domino-server.our-internal-domain Hello mytestbox ([192.168.17.1]), pleased to meet you

MAIL FROM: <me@my-real-address.com>

451 Unable to complete command, DNS not available or timed out

And that's it.

After I enter the MAIL FROM line, the server immediately responds with 451. This leads me to believe that there is actually no DNS timeout involved. I've watched the link with tcpdump and I see some DNS traffic (successful lookups for mytestbox.our-internal-domain) when I initiate the connection, but none at all after I enter the MAIL FROM line.

We've checked and double-checked the server configuration documents and can't see anything wrong.

All DNS lookups (forward and reverse) work fine from Linux command line.

What might it be?